package linkedlist.leetcode_142;

/**
 * 返回有环链表的入环节点
 */
public class Solution {
    public static void main(String[] args) {
            ListNode l1 = new ListNode(1);
            ListNode l2 = new ListNode(2);
            ListNode l3 = new ListNode(3);
            ListNode l4 = new ListNode(2);
            ListNode l5 = new ListNode(1);
            ListNode l6 = new ListNode(2);
            l1.next = l2;
            l2.next = l3;
            l3.next = l4;
            l4.next = l5;
            l5.next = l6;
            l6.next = l3;
            detectCycle(l1);
    }
    public static ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(true){
            //完美的edge-cases判断，防止空指针。
            if(fast == null || fast.next == null){
                return null;
            }

            //快指针一次走2步，慢指针一次走1步。
            fast = fast.next.next;
            slow = slow.next;

            //相等证明有环，此处是地址值相等。
            if(fast == slow){
                break;
            }
        }

        //有环，令fast指针从头开始，一次走1步，再次相遇即是入环节点。
        fast = head;
        while(fast != slow){
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}
